package code.oldCode.classic150;

import java.util.*;

/**
 * @author cuihaoran
 * @date 2024/12/17
 */
public class Classic150_doublePointer {
    /* 125. 验证回文串 */
    public boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if ('a' <= s.charAt(i) && s.charAt(i) <= 'z')
                sb.append(s.charAt(i));
            else if ('A' <= s.charAt(i) && s.charAt(i) <= 'Z')
                sb.append((char) (s.charAt(i) + 'a' - 'A'));
            else if ('0' <= s.charAt(i) && s.charAt(i) <= '9')
                sb.append(s.charAt(i));
        }
        String s_new = sb.toString();
        int left = 0, right = s_new.length() - 1;
        while (left < right) {
            if (s_new.charAt(left) != s_new.charAt(right))
                return false;
            left++;
            right--;
        }

        return true;
    }

    /* 392. 判断子序列 */
    public boolean isSubsequence(String s, String t) {
        int lenS = s.length();
        int lenT = t.length();
        int posS = 0, posT = 0;
        while (posT < lenT && posS < lenS) {
            if (s.charAt(posS) == t.charAt(posT))
                posS++;
            posT++;
        }
        return posS == lenS;
    }

    /* 167. 两数之和 II - 输入有序数组 */
    public int[] twoSum(int[] numbers, int target) {
        // O(n)+O(n)
        int len = numbers.length;
        int[] ans = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            if (map.containsKey(target - numbers[i])) {
                ans[0] = map.get(target - numbers[i]);
                ans[1] = i + 1;
                return ans;
            } else {
                map.put(numbers[i], i + 1);
            }
        }
        return ans;
    }

    public int[] twoSum_noHash_betterSolution(int[] numbers, int target) {
        // O(n)+O(1)
        int len = numbers.length;
        int left = 0, right = len - 1;
        while (left < right) {
            if (numbers[left] + numbers[right] == target) {
                return new int[]{left + 1, right + 1};
            } else if (numbers[left] + numbers[right] > target) {
                right--;
            } else {
                left++;
            }
        }
        return null;
    }

    /* 11. 盛最多水的容器 */
    public int maxArea(int[] height) {
        int len = height.length;
        int best = 0;
        int left = 0, right = len - 1;
        while (left < right) {
            int now = (right - left) * Math.min(height[left], height[right]);
            best = Math.max(best, now);
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return best;
    }

    /* 15. 三数之和 */
    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);
        Map<Integer, Integer> map = new HashMap<>();
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            map.put(nums[i], i);
        }
        // [-4,-1,-1,0,1,2]
        // [[-1,-1,2],[-1,0,1]]
        // 要保证不要重复选，i选第一个，j选第二个，hashmap找第三个
        for (int i = 0; i < len - 2; i++) {
            // 如果第一个和上一个重复，不选，因为会重复
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            for (int j = i + 1; j < len - 1; j++) {
                // 如果第二个和上一个重复，不选，因为会重复
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;
                int nowNeed = -(nums[i] + nums[j]);
                if (map.containsKey(nowNeed) && map.get(nowNeed) > j) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nowNeed);
                    lists.add(list);
                }
            }
        }

        return lists;
    }

    /* 209. 长度最小的子数组 O(nlogn) */
    public int minSubArrayLen(int target, int[] nums) {
        // 看上去是个背包问题(?).其实不是,他要求子数组是下标连续的.用前缀和,O(nlogn)
        int len = nums.length;
        int[] sum = new int[len + 1];
        int ans = Integer.MAX_VALUE;
        // 算前缀和数组
        for (int i = 1; i <= len; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        // 循环遍历，遍历到的每个元素最为起点，找和大于等于target的位置
        for (int i = 1; i <= len; i++) {
            // 二分查找，找到位置j使得sum[j] - sum[i - 1] >= target, 意思是第i-j个的和大于等于target, 即找target + sum[i - 1]
            int findNum = target + sum[i - 1];
            // Arrays.binarySearch返回插入位置
            int findPos = Arrays.binarySearch(sum, findNum);
            // 如果为正，说明找到了，返回 (插入位置)；如果为负，说明没找到，返回 -插入位置-1
            if (findPos < 0) {
                findPos = -(findPos + 1);
            }
            if (findPos <= len) {
                ans = Math.min(ans, findPos - (i - 1));
            }
        }

        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}
